备用返回通道

转到题目

思路引导:

问题定性:

首先观察样例规模与要求，发现深度为$ 10^4$ 的树的求解问题，光搜索就达$2^{10^4}-1,$ 暴力显然不可 根据经验:正难则反，这道题，显然是让我们分析值域性质，是一类数学归纳或计数问题 而且，我们发现，这个题目最多、极限下，也就支持$O(n^2)$ 我们一步步，从更可能的角度切入

思路总结:

根据题目，对问题进行拆分: 先逆向思考,符合要求的路径转化为:

• A类路径有多少
• B类路径有多少

根据问题归纳规律，可以得到答案

代码:

n = int(input())
MOD = 1000000007
if (n<3):
    print(((2**n-1)- 2**(n-1))%MOD)
else:
    print(((2**n -4)+(2**n-1)- 2**(n-1))%MOD)